Composition proof
$$ \def\F{\mathbb F} $$
Context. Are values are from a
Goal. Given $P\in\F_{< N}[X]$ Proof the following constraint using Schwartz-Sippel and a $\le N$ low degree test:
$$ F(G(X)) \mod H(X) = 0 $$
$$ \frac{P(X)^{2^{64}} - 1}{X^N - 1} $$
Lemma. Polynomials satisfying the above constraint satisfy $P(\omega_N^i) = \omega_{2^{64}}^{k_i}$ for $i \in [0,N)$.
Definition. $\F_{< N}[X] \sim \F[X]/ X^N$
Assume for the moment $N = 2^{64}$, we can generalize later
$$ \frac{P(X)^N - 1}{X^N - 1} $$
This puts some constraints on the coefficients of $P$.
$$ P(X) = \sum_{i\in[0,N)} p_i X^i $$
$$ \frac{P(X)^N - 1}{X^N - 1} = \frac{\left(\sum_{i\in[0,N)} p_i X^i\right)^N - 1}{X^N - 1} $$
We can now expand using something like the https://en.wikipedia.org/wiki/Binomial_theorem, i.e. https://en.wikipedia.org/wiki/Multinomial_theorem.
To do. Look into differentials.
Simplifications
We can further restrict the problem to the case $h(x) = x^n - 1$. This can help because we can now factor $h$ as
$$ h(x) = (x - ω_n^0) (x - ω_n^1) (x - ω_n^2) \cdots (x - ω_n^{n-1}) $$
or (thanks Yan Zhang)
$$ h(x) = (x - 1) (x + 1) (x^2 + 1) (x^4 + 1) \cdots (x^n + 1) $$
The problem could be broken solved modulo these factors and then invoke CRT.
